#include <stdio.h>
#include <stdlib.h>

int max_sub(int arr[], int length, int* start, int* end)
{
  int sum = 0, maxsum = 0, i, j;
  int* sum_arr = (int*)malloc( (length+1)*sizeof(int) );
  *start = -1;
  *end = -1;
  //preprocessing
  for(i = 0,sum_arr[0] = 0; i<length; ++i)
    sum_arr[i+1] = sum_arr[i] + arr[i];

  for(i = 0; i<length; ++i) {
    for(j = i; j<length; ++j) {
      sum = sum_arr[j+1]-sum_arr[i];
      if(sum > maxsum){
	maxsum = sum;
	*start = i;
	*end = j;
      }
    }
  }
  return maxsum;
}

int main()
{
  int arr[] = {31,-41,59,26,-53,58,97,-93,-23,84};
  int i,j, maxsum;
  for(i = 0; i<10; ++i)
    printf("%d\t",arr[i]);
  puts("");

  maxsum = max_sub(arr, 10, &i, &j);
  if(maxsum > 0){
    printf("The maximum subarray is from %d to %d\n",arr[i],arr[j]);
    printf("The maximum sub is %d\n", maxsum);
  }
  
  return 0;
}
